package compiler.tac;

import java.util.ArrayList;

import compiler.dot.GraphHelper;
import compiler.symboltable.SymbolTable.Item;
import compiler.tac.Instruction.Operator;

public class BasicBlock {
	private ArrayList<Instruction> code = new ArrayList<Instruction>();
	private ArrayList<BasicBlock> predecessors = new ArrayList<BasicBlock>();
	protected ArrayList<BasicBlock> successors = new ArrayList<BasicBlock>();
	private int order;
	private String lable;
	private boolean hasReturnValue = false;

	protected ArrayList<BasicBlock> domChildren = new ArrayList<BasicBlock>();
	protected  ArrayList<BasicBlock> domF = new ArrayList<BasicBlock>();
	
	boolean processed = false;
	public static void add(BasicBlock parent, BasicBlock child) {
		parent.addSuccessor(child);
		child.addPredcessor(parent);
	}
	
	public ArrayList<BasicBlock> getDomF()
	{
		return domF;
	}
	public ArrayList<BasicBlock> calDomF()
	{
		for(BasicBlock child : successors)
			if(domChildren.indexOf(child) == -1)
			{
				this.domF.add(child);
				//child.domFF.add(this);
			}
		for(BasicBlock domChild : domChildren)
			for(BasicBlock b : domChild.calDomF())
				if(this.domChildren.indexOf(b)==-1 && this.domF.indexOf(b)==-1)
				{
					this.domF.add(b);
				}

		return domF;
	}
	
	
	//rename variables during constructing SSA
	public int rename(Item v, int count, NameStack name)
	{
		int AssignCount = 0;
		if(this.code.size()>0)
		for(Instruction inst : this.code)
		{
			if(inst.oprt==Operator.Mv && inst.dest.getId().equals(v.getName()))
			{
				if(inst.oprdl!=null && inst.oprdl.getId()!=null)
					if(inst.oprdl.getId().equals(v.getName()))
						inst.oprdl.setId(v.getName()+"_"+name.top());
				if(inst.oprdr!=null && inst.oprdr.getId()!=null)
					if(inst.oprdr.getId().equals(v.getName()))
						inst.oprdr.setId(v.getName()+"_"+name.top());
				AssignCount ++;
				count++;
				inst.dest.setId(v.getName()+"_"+count);
				name.push(count);
			}
			if(inst.oprt==Operator.Phi && inst.dest.getId().equals(v.getName()))
			{
				AssignCount++;
				count++;
				inst.dest.setId(v.getName()+"_"+count);
				name.push(count);
			}
			if(inst.oprt != Operator.Phi)
			{
				if(inst.oprdl!=null && inst.oprdl.getId()!=null)
				{
					if(inst.oprdl.getId().equals(v.getName()))
						inst.oprdl.setId(v.getName()+ "_" +name.top());
				}
				if(inst.oprdr!=null && inst.oprdr.getId()!=null)
				{
					if(inst.oprdr.getId().equals(v.getName()))
						inst.oprdr.setId(v.getName()+ "_" +name.top());
				}
			}
		
		}
		
		for(BasicBlock s : this.successors)
		{
			int j = s.getPreds().indexOf(this);
			for(Instruction inst: s.code)
			{
			
				if(inst.oprt==Operator.Phi && SimpleExpt.cutName(inst.dest.getId()).equals(v.getName()))
				{
					inst.phiArg.get(j).setId(v.getName()+ "_" + name.top());
				}
			}	
		}
		
		if(domChildren!=null && domChildren.size()>0)
			for(BasicBlock domchild : domChildren)
			{
				count = domchild.rename(v, count, name);
			}
		for(int i = 0; i < AssignCount; i ++)
			name.pop();
		return count;
	}
	
	//rename for expression
	public ExptNameStack renameE(SimpleExpt expt, ExptNameStack stack)
	{
		
		int AssignCountE = 0;
		int AssignCountl = 0;
		int AssignCountr = 0;
		for(Instruction inst : code)
		{
			if(inst.dest!=null && inst.dest.getId()!=null && SimpleExpt.cutName(inst.dest.getId()).equals(expt.opl))
			{
				stack.curOpl.push(SimpleExpt.getVersion(inst.dest.getId()));
				AssignCountl++;
			}
			if(inst.dest!=null && inst.dest.getId()!=null && SimpleExpt.cutName(inst.dest.getId()).equals(expt.opr))
			{
				stack.curOpr.push(SimpleExpt.getVersion(inst.dest.getId()));
				AssignCountr++;
			}
			if(inst.oprt == Operator.BigPhi && inst.dest.getId().equals(expt.toString()))
			{
				AssignCountE ++;
				stack.count++;
				inst.dest.setId(expt.toString()+"["+stack.count+"]");
				int vl=-1,vr=-1;
				if(stack.curOpl != null && stack.curOpl.size()>0)
					vl = stack.curOpl.top();
				if(stack.curOpr != null && stack.curOpr.size()>0)
					vr = stack.curOpr.top();
				stack.push(stack.count, vl, vr);
				stack.curOpl.push(vl);
				stack.curOpr.push(vr);

			}
			if(inst.exptVersion!=null && inst.exptVersion.equals(expt.toString()))
			{
				if(stack.exptVersion.size()>0 && stack.match(SimpleExpt.getVersion(inst.oprdl.getId()),SimpleExpt.getVersion(inst.oprdr.getId())))
					inst.exptVersion += "["+stack.exptVersion.top()+"]";
				else {
					AssignCountE++;
					stack.count++;
					inst.exptVersion += "["+stack.count + "]";
					stack.push(stack.count,SimpleExpt.getVersion(inst.oprdl.getId()),SimpleExpt.getVersion(inst.oprdr.getId()));
					stack.curOpl.push(stack.oplVersion.top());
					stack.curOpr.push(stack.oprVersion.top());
				}
			}
		}
		
		for(BasicBlock s: successors)
		{
			int j = s.getPreds().indexOf(this);
			if(s.code!=null && s.code.size()>0)
				for(Instruction inst: s.code)
					if(inst.oprt == Operator.BigPhi && SimpleExpt.cutName(inst.dest.getId()).equals(expt.toString()))
					{
						if(stack.exptVersion.size() > 0 && stack.curOpl.size()> 0 && stack.curOpl.top()==stack.oplVersion.top() 
								&& stack.curOpr.size()>0 && stack.curOpr.top()==stack.oprVersion.top())
							inst.phiArg.set(j, new Address(expt.toString()+ "["+stack.exptVersion.top()+"]"));
						else {
							inst.phiArg.set(j, new Address(expt.toString()+"[-1]"));
							//System.out.println("insert -1 version of block "+ s.getOrder() + " now in " + this.order);
						}
					}
						
		}
		
		for(BasicBlock child: domChildren)
			stack = child.renameE(expt, stack);
		for(int i= 0; i < AssignCountl; i++)
		{
			stack.curOpl.pop();
		}
		for(int i= 0; i < AssignCountr; i++)
		{
			stack.curOpr.pop();
		}
		for(int i =0; i < AssignCountE; i ++)
		{
			stack.pop();
		}
		
		return stack;
	}
	
	public boolean calhasrealuse(SimpleExpt expt, int version)
	{
		processed = true;
		boolean occur = false;
		
		if(containOccrencetoE(expt,version))
		{
			return true;
		}
		else if(containBigPhitoE(expt, version))
		{
			return false;
		}
		else {
			for(BasicBlock pre: getPreds())
				if(!pre.processed && pre.calhasrealuse(expt, version))
				{
					occur = true;
					break;
				}
		}
		return occur;
	   // inst.hasrealuse.set(inst.phiArg.indexOf(add), occur);
	}
	public Instruction insert(SimpleExpt expt)
	{
		Instruction instruction= new Instruction(expt.oprt, null, new Address(expt.opl), new Address(expt.opr));
		instruction.exptVersion=expt.toString();
		code.add(instruction);
		return instruction;
	}
	public static void remove(BasicBlock parent, BasicBlock child) {
		parent.removeSuccessor(child);
		child.removePredcessor(parent);
	}
	
	public void printCFG(GraphHelper graph) {
		String label = getName();
		if (lable != null) {
			label += " ["+lable+"]";
		}
		label += ":";
		
		for (Instruction inst : code) {
			label += "\\l" + inst.toString();
		}
		
		boolean fresh = graph.addNode(this, label);
		
		if (fresh) {
			for (BasicBlock succ : successors) {
				succ.printCFG(graph);
				graph.addEdge(this, succ);
			}
		}
	}

	public void printDT(GraphHelper graph) {
		graph.addNode(this, getName());
		
		for (BasicBlock child : domChildren) {
			child.printDT(graph);
			graph.addEdge(this, child);
		}
	}
	
	public int size() {
		return code.size();
	}
	
	public void addDomChild(BasicBlock child) {
		if (domChildren.contains(child)) {
			return;
		}
		
		domChildren.add(child);
	}
	
	public ArrayList<BasicBlock> getDomChildren() {
		return domChildren;
	}
	
	public String getName() {
		return "B"+order;
	}
	
	public int getOrder() {
		return order;
	}
	
	public void setOrder(int odr) {
		this.order = odr;
	}
	
	public boolean hasReturnValue() {
		return hasReturnValue;
	}

	public void setHasReturnValue(boolean rv) {
		this.hasReturnValue = rv;
	}
		
	public ArrayList<Instruction> getInstructions() {
		return code;
	}
	
	public ArrayList<BasicBlock> getPreds() {
		return predecessors;
	}
	
	public ArrayList<BasicBlock> getSuccs() {
		return successors;
	}
	
	public void addPreEmptBlock(ThreeAddressCode tac)
	{
		BasicBlock b = new BasicBlock();
		tac.addBlock(b);
		for(BasicBlock prev: this.predecessors)
		{	
			prev.removeSuccessor(this);
			BasicBlock.add(prev, b);
		}
		this.removeAllPredecessor();
		BasicBlock.add(b, this);
	}
	private void removeSuccessor(BasicBlock succ) {
		successors.remove(succ);
	}
	
	private void removeAllPredecessor() {
		int size = predecessors.size();
		for(int i = size-1; i >= 0; i --)
			predecessors.remove(i);
	}
	
	private void addSuccessor(BasicBlock succ) {
		if (successors.contains(succ)) {
			return;
		}
		
		successors.add(succ);
	}
	
	private void removePredcessor(BasicBlock pred) {
		predecessors.remove(pred);
	}
	
	private void addPredcessor(BasicBlock pred) {
		if (predecessors.contains(pred)) {
			return;
		}
		
		predecessors.add(pred);
	}
	
	public void setLable(String la)
	{
		this.lable = la;
	}
	
	public String getLable()
	{
		return this.lable;
	}
	// for Add, Sub, Mul, Div, Cmp
	public void addBinaryInstruction(Operator oprt, String dest, String oprdl, String oprdr) {
		code.add(new Instruction(oprt, new Address(dest), new Address(oprdl), new Address(oprdr)));
	}
	
	// for Neg, Load, Move
	public void addUnaryInstruction(Operator oprt, String dest, String oprd) {
		code.add(new Instruction(oprt, new Address(dest), new Address(oprd), null));
	}

	// for Bra
	public void addJumpInstruction(BasicBlock target, String lab) {
		code.add(new Instruction(Operator.Bra, null, new Address(target), null, lab));
		target.setLable(lab);
	}
	
	// for Beq, Bne, Blt, Ble, Bgt, Bge
	public void addBranchInstruction(Operator oprt, String cmp, BasicBlock target,String lab) {
		code.add(new Instruction(oprt, null, new Address(cmp), new Address(target), lab));
		target.setLable(lab);
	}
	
	// for Store
	public void addStoreInstruction(String address, String data) {
		code.add(new Instruction(Operator.Str, null, new Address(address), new Address(data)));
	}
	
	// for Read
	public void addReadInstruction(String dest) {
		code.add(new Instruction(Operator.Rd, new Address(dest), null, null));
	}
	
	// for Write
	public void addWriteInstruction(String oprd) {
		code.add(new Instruction(Operator.Wrt, null, new Address(oprd), null));
	}
	
	// for End
	public void addEndInstruction() {
		code.add(new Instruction(Operator.End, null, null, null,null));
	}
	
	// for Phi
	public void addPhiInstruction(String dest, int numberofpredecessor) {
		code.add(0,new Instruction(new Address(dest),numberofpredecessor));
	}
	
	//for BigPhi
	public void addBigPhiInstruction(SimpleExpt expt, int numberofpredecessor)
	{
		if(!this.containPhitoE(expt))
			code.add(0,new Instruction(expt, numberofpredecessor));
		else {
			for(int i = code.size()-1; i>=0; i --)
			{
				if(code.get(i).oprt==Operator.Phi && (SimpleExpt.cutName(code.get(i).dest.getId()).equals(expt.opl)
													||SimpleExpt.cutName(code.get(i).dest.getId()).equals(expt.opr)))
					if(i < code.size()-1)
						code.add(i+1,new Instruction(expt, numberofpredecessor));
					else 
						code.add(new Instruction(expt, numberofpredecessor));
			}
		}
	}
	//for parameters
	public void addParamInstruction(String dest)
	{
		code.add(new Instruction(Operator.Prm, new Address(dest), null, null));
	}
	//for call
	public void addCallInstruction(String funcAddr)
	{
		code.add(new Instruction(Operator.Call, new Address(funcAddr), null, null));
	}
	
	//for return
	public void addReturnInstruction()
	{
		code.add(new Instruction(Operator.Rtn, null, null, null));
	}
	
	public boolean isExit()
	{
		return false;
	}
	
	public boolean containAssigntoV(Item v)
	{
		for(Instruction inst: this.code)
		{
			//System.out.println(inst.oprt + " " + inst.dest.getId());
			if(inst.oprt == Operator.Mv && inst.dest.getId().equals(v.getName()))
				return true;
		}
				
		return false;		
	}
	
	public boolean containPhitoE(SimpleExpt E)
	{
		for(Instruction inst : this.code)
		{	
			if(inst.oprt == Operator.Phi && (SimpleExpt.cutName(inst.dest.getId()).equals(E.opl)||
											 SimpleExpt.cutName(inst.dest.getId()).equals(E.opr)))
				return true;
		}	
		return false;
	}
	
	public boolean containOccrencetoE(SimpleExpt E)
	{
		for(Instruction inst : this.code)
		{	
			if(inst.exptVersion !=null && SimpleExpt.cutName(inst.exptVersion).equals(E.toString()))
				return true;
		}	
		return false;
	}
	public boolean containBigPhitoE(SimpleExpt E)
	{
		for(Instruction inst: this.code)
		{
			if(inst.dest!=null && inst.dest.getId()!=null)
				if(inst.oprt == Operator.BigPhi && SimpleExpt.cutName(inst.dest.getId()).equals(E.toString()))
					return true;
		}
		return false;
	}
	
	public boolean containOccrencetoE(SimpleExpt expt, int version)
	{
		String nameString = expt.toString()+"["+version+"]";
		for(Instruction inst:code)
			if(inst.exptVersion !=null && inst.exptVersion.equals(nameString))
				return true;
		return false;
	}
	
	public boolean containBigPhitoE(SimpleExpt expt, int version)
	{
		String nameString = expt.toString()+"["+version+"]";
		for(Instruction inst:code)
			if(inst.oprt==Operator.BigPhi && inst.dest.getId().equals(nameString))
				return true;
		return false;
	}
	
	public Instruction getBigPhiInstruction(SimpleExpt expt)
	{
		if(code!=null && code.size()>0)
		for(Instruction inst:code)
			if(inst.oprt==Operator.BigPhi && SimpleExpt.cutName(inst.dest.getId()).equals(expt.toString()))
				return inst;
		return null;
	}
}
